package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.Learning.AlgorithmTemplate
 * @File : _2_6Heap.java
 * @Author : WangRuoyu
 * @Date 2023/3/12 14:55
 */

public class _2_6Heap {
    private int[] data = new int[100010];
    private int size = 0;

    private void down(int x) { // 向下调整x位置的元素
        int t = x;
        if (2 * x + 1 < size && data[2 * x + 1] < data[t]) {
            t = 2 * x + 1;
        }
        if (2 * x + 2 < size && data[2 * x + 2] < data[t]) {
            t = 2 * x + 2;
        }
        if (t != x) {
            int p = data[x];
            data[x] = data[t];
            data[t] = p;
            down(t);
        }
    }

    private void up(int x) { // 向上调整x位置的元素
        if (x == 0) {
            return;
        }
        int t = x;
        if (x % 2 == 0) {
            if (data[(x - 1) / 2] > data[t]) {
                t = (x - 1) / 2;
            }
        } else {
            if (data[x / 2] > data[t]) {
                t = x / 2;
            }
        }
        if (t != x) {
            int p = data[x];
            data[x] = data[t];
            data[t] = p;
            up(t);
        }
    }

    public void insert(int x) { // 在插入最后插入数据，然后执行up操作
        data[size] = x;
        up(size);
        size++;
    }

    public void insert(int[] x) {
        for (int j : x) {
            insert(j);
        }
    }

    public int minValue() { // 返回最小值，即堆顶元素
        return size == 0 ? -1 : data[0];
    }

    public int size() { // 返回堆的大小
        return size;
    }

    public void deleteMinValue() { // 删除最小值，即堆顶元素
        if (size == 0) {
            return;
        }
        --size;
        data[0] = data[size];
        down(0);
    }

    public void delete(int k) { // 删除第k个元素
        if (k - 1 >= size) {
            return;
        }
        data[k - 1] = data[--size];
        up(k - 1);
        down(k - 1);
    }

    public void change(int k, int x) { // 改变第k个元素的值
        if (k - 1 >= size) {
            return;
        }
        data[k - 1] = x;
        up(k - 1);
        down(k - 1);
    }

    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
}